In a trace compiler, a trace is a single-entry multiple-exit region formed out of instructions following a real execution path. Trace-based code optimizers compile traces, which are sequences of executed instructions formed at runtime. Such code optimization was initially proposed for binary optimizers where static program information is not available. Examples of trace-based optimization systems include binary translators such as DynamoRIO™, and trace-based just-in-time (JIT) compiler such as TraceMonkey™ the Javascript JIT from Firefox™.
Trace selection refers to a process that forms traces out of executed instructions at runtime. The current dominant approach in trace-driven optimizers utilizes two-step next-executing-tail (NET) type of selection. The two-step NET type of selection profiles frequently executed basic blocks (BB) as the trace head; once the trace head is selected, instructions executed next are recorded the trace. In NET selection, traces are initially built from targets of backward branches and grow gradually out of side-branches (side-exits) of existing traces. Trace size is determined by the termination conditions used in trace recording. Once a trace head is selected, trace formation is determined by the very path taken at trace recording time.
Another approach is a path profiling approach in which the frequently executed paths are profiled as traces. Compared to the NET approach, this approach may be more accurate in capturing of hot paths, but may require high overhead. Due to the high profiling overhead, the path profiling approach often requires special hardware support, thus are rarely used in real trace compilers.
The ability to incorporate runtime (profiling) information into the compilation scope is one advantage of compiling traces over compiling statically defined program scopes such as methods or loops. However, there is limitation in how profiling information is used in NET style trace selection. Except for trace head selection, profiling information is not used in the formation of the trace. For example, the trace recording step uses no history data. As a result, it may introduce pathologic formations or very different formations across multiple runs of a program. Once a trace is formed and compiled, profiling the execution of a trace often requires the trace compiler instrument binary traces, and utilizing the profiling information for better code generation requires recompilation of the trace.